package 测试;

public class 需要排序最短子数组的长度 {

	public static void main(String[] args) {
		int[] a = { 1, 2, 3, 8, 7, 6, 5, 51, 52, 53 };
		int[] b = { 1, 2, 3, 8, 7, 6, 5, 51, 52, 53, 41, 42, 43, 100, 101, 102 };
		System.out.println(new ShortSubsequence().findShortest(a, a.length));
		System.out.println("======================");
		System.out.println(new ShortSubsequence().findShortest(b, b.length));
	}

	public static class ShortSubsequence {
		public int findShortest(int[] A, int n) {
			if (A == null || n <= 1)
				return 0;

			int max = A[0], min = A[n - 1];
			int highIndex = 0, lowIndex = 0;

			for (int i = 1; i < n; i++) {
				if (A[i] >= max) {
					// 记录最大值
					max = A[i];
				} else {
					// 记录不大于最大值的最后一个位置(正序递减区域中的最后一个位置)
					highIndex = i;
				}
			}

			for (int i = n - 2; i >= 0; i--) {
				if (A[i] <= min) {
					// 记录最小值
					min = A[i];
				} else {
					// 记录不小于最小值的最后一个位置(逆序第增区域中的最后一个位置)
					lowIndex = i;
				}
			}

			System.out.println(max + " " + min);
			System.out.println(highIndex + " " + lowIndex);
			System.out.println(A[highIndex] + " " + A[lowIndex]);

			if (highIndex == 0 || lowIndex == 0)
				return 0;
			return highIndex - lowIndex + 1;

		}
	}

	public class ShortSubsequence2 {
		public int findShortest(int[] A, int n) {
			if (A == null || n <= 1) {
				return 0;
			}

			int indexMin = 0;
			int indexMax = n - 1;
			int i = 0, j = n - 1;

			while (i != n - 1 && A[++i] >= A[indexMin++])
				;
			if (i == n - 1)
				return 0;

			while (A[--j] <= A[indexMax--])
				;

			int max = A[j], min = A[i];
			for (int k = i - 1; k <= j + 1; k++) {
				max = Math.max(A[k], max);
				min = Math.min(A[k], min);
			}

			i = 0;
			j = n - 1;
			while (A[i++] <= min)
				;
			while (A[j--] >= max)
				;

			return j - i + 3;
		}
	}
}
